package leetcode_数组.leetcode_前缀和数组;

/**
 * 二维区域和 检索 - 矩阵不可变
 * 使用缓存行的办法
 * 二维数组是由一维数组组成的
 * 结果可以是一行一行加起来的
 */
public class _304 {
    static class NumMatrix {
        private int[][] prefixSum;

        public NumMatrix(int[][] matrix) {
            if (matrix.length != 0) {
                prefixSum = new int[matrix.length][matrix[0].length + 1];
                for (int i = 0; i < matrix.length; i++) {
                    for (int j = 1; j <= matrix[0].length; j++) {
                        prefixSum[i][j] = prefixSum[i][j - 1] + matrix[i][j - 1];
                    }
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int res = 0;
            for (int i = row1; i <= row2; i++) {
                res += prefixSum[i][col2 + 1] - prefixSum[i][col1];
            }
            return res;
        }
    }

    /**
     * 最优解
     * 使用 dp 数组记录 [i, j] 到 [0, 0] 之间所有数的和 , 即 i * j 矩阵的和
     * dp[i][j] : [i-1, j-1] 到 [0, 0] 之间所有数的和
     * dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]
     */
    static class NumMatrix_perfect {
        private int[][] dp;

        public NumMatrix_perfect(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return;
            }
            dp = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 1; i <= matrix.length; i++) {
                for (int j = 1; j <= matrix[0].length; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            // 在图上画一下就能得出这个式子了
            return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
        }
    }
}
